package com.heima.leetcode.practice;

import java.util.Arrays;

/**
 * leetcode 300 最长递增子序列
 * @author 勾新杰
 * @version 1.0
 * @date 2024/11/12 10:07
 */
public class E300 {
    /*
        先求子问题，记录的是有可能的最长递增子序列
        1    3    6    7    9    4    10   5    6
        1    1    1    1    1    1    1    1    1
             2    1    1    1    1    1    1    1
                  3    1    1    1    1    1    1
                       4    1    1    1    1    1
                            5    1    1    1    1
                                 3    1    1    1
                                      6    1    1
                                           4    1
                                                5
     */

    /**
     * <h3>方法一：动态规划</h3>
     * 最长递增子序列
     * @param nums 数组
     * @return 最长子序列的长度
     */
    public int lengthOfLIS1(int[] nums) {
        // 1. 定义一个数组 dp，其中 dp[i] 表示以第 i 个元素结尾的最长递增子序列的长度
        int[] dp = new int[nums.length];
        // 2. 初始化 dp 数组，所有值设为 1，因为每个元素自身可以看作一个长度为 1 的递增子序列。
        Arrays.fill(dp, 1);
        // 3. 遍历数组，对于每个元素，再向前遍历其之前的所有元素，如果当前元素大于之前的某个元素，则更新 dp 数组。
        for (int i = 1; i < nums.length; i++) {
            for (int j = 0; j < i; j++){
                if (nums[i] > nums[j]){
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
        }
        // 4. 最后，dp 数组中的最大值即为最长递增子序列的长度。
        int max = 0;
        for (int i : dp) {
            max = Math.max(max, i);
        }
        return max;
    }

    /*
       创建一个最大大小为nums.length的临时数组tails，其中tails[i]记录的是
       所有i+1长度的递增子序列中最后一个元素最小的递增子序列对应的最后一个元素
       例如 tails[0]最后就是所有长度为1的递增子序列中最后一个元素最小的递增子序列对应的尾元素
       然后每次遍历到一个元素，就应该找到可以和哪个序列构成一个更长的序列，也就是找到合适的位置
       如果尾元素更小，则更新，如果没有尾元素，长度加一
     */

    /**
     * <h3>方法二：引入二分查找和临时数组进行优化</h3>
     * 最长递增子序列
     * @param nums 数组
     * @return 最长子序列的长度
     */
    public int lengthOfLIS2(int[] nums) {
        // 1. 创建tails数组，tails[i]最终用来记录长度为i+1的所有递增子序列尾元素的最小值
        int[] tails = new int[nums.length];
        int length = 0; // 用于记录最小值
        for (int num : nums) {
            // 二分查找num应该放在tails数组中的位置
            int left = 0, right = length;
            while (left < right) {
                int median = (left + right) >>> 1;
                if (tails[median] < num) {
                    left = median + 1;
                } else {
                    right = median;
                }
            }
            tails[left] = num; // 更新该位置
            if (left == length) {
                length++;
            }
        }
        return length;
    }
}
